package com.atguigu.main.search;

/**
 * @author ：剧情再美终是戏
 * @description：矩阵查找(二分查找变种)
 * @mail : 13286520398@163.com
 * @date ：Created in 2020/2/28 19:40
 * @modified By：
 * @version: 1.0
 */
public class MatrixSearch {
    public static void main(String[] args) {
        int[][] matrix = { // i * j
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 50}
        };

        System.out.println(matrixSearch(matrix, 16));
    }

    public static boolean matrixSearch(int[][] matrix, int target) {
        // 参数过滤
        if (matrix.length == 0) return false;

        // 每次判断第一组元素的最后一个元素
        int i = 0;
        int j = matrix[i].length - 1;
        while (i < matrix.length && j >= 0) {
            int compare = matrix[i][j];
            if (target == compare) {
                return true;
            } else if (target > compare) { // 如果目标元素比最后一个元素要大的话，循环下一组数据
                i += 1;
            } else if (target < compare) { // 如果目标元素比最后一个元素要小的话，就循环组内的数据
                j -= 1;
            }
        }
        return false;
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        System.out.println(matrix.length);
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                System.out.println(matrix[i][j]);
                return true;
            } else if (matrix[i][j] > target) {
                j -= 1;
            } else {
                i += 1;
            }
        }
        return false;
    }
}
